package com.modsaid;

/**
 * @author Mahmoud Said  mahmoud@modsaid.com
 * 
 *	this class generates the sequence of prime numbers
 *
 */
public class PrimeNumbersGenerator 
{
	public static void main( String[] args ){
		System.out.println("Generating prime numbers:");
    	PrimeNumbersGenerator generator = new PrimeNumbersGenerator();
    	generator.generatePrimes();
    }
	
	private long upperLimit;

	PrimeNumbersGenerator(){
		this.upperLimit = this.getMaxLong();
	}

	PrimeNumbersGenerator(long maxValue){
		this.upperLimit = maxValue;
	}

    /**
     * find the value of the largest number that can be held in a long data type
     * using bits shifting and ORing with 1 
     * @return the largest long value
     */
    private long getMaxLong(){
    	long max=0;
    	long i=1;
    	while(i>0){
    		max=i;
        	i= i<<1;
        	i = i | 1;
    	}
    	return max;
    }

    
    /**
     * starting with 2, 3  then check next odd numbers, this method points out prime numbers
     */
    public void generatePrimes(){
    	long [] primes = new long[Integer.MAX_VALUE>>10];
    	Integer lastIndex = 0;
    	long number = 2;
    	mark(number);
    	number=3;
    	while(number<this.upperLimit){
    		if (checkPrime(number, primes, lastIndex)){
    			primes[lastIndex]=number;
    			lastIndex++;
    			mark(number);
    		}
    		number+=2;
    	}
    }

    /**
     * @param number: number to check
     * @param primes: prime number found so far
     * @param lastIndex the index of the last of the first empty location in the primes 
     * 			array (the index in the array where the number will be store if proved prime) 
     * 
     * @return 	true if the given number is prime
     * 			false if the given number is not prime
     */
    private boolean checkPrime(long number, long [] primes, Integer lastIndex){
    	long rootLimit = this.getRootLimit(number);
    	for(Integer i=0; i<lastIndex && i < rootLimit;i++){
    		if (number % primes[i] == 0)
    			return false;
    	}
    	return true;
    }
    
    private static Integer count = 0;
    
    /**
     * this method is responsible for handling prime numbers when found. currently it just prints them 
     * out to the console
     * @param prime
     */
    private void mark(long prime){
    	System.out.println(++count+":\t"+prime);
    }
    
	
    /**
     * this method returns a value with the half number of bit (just larger than 
     * the possible root). 
     * @param number
     * @return stopping limit slightly larger than the root of the given number
     */
    public long getRootLimit(long number){
    	if (number==0) return 0;
    	int i =0;
    	while(number>0){
    		i++;
    		number = number >> 1;
    	}
    			 		//i holds the number of bits used to represent number
    	i=i>>1; 		//divide by 2 to get the half number of bits
    	long one=1;
    	return (one<<i);
    }
}





